The Internet of Things (IoT) is widely and increasingly prevalent, which provides communication capabilities to various devices in the world to thereby allow the devices to perform remote measurements and realize the utilization of information collected from them. In the use of the IoT technology, there are needs for the development of technologies enabling more efficient management of vast amounts of information collected by various kinds of devices and faster search for desired information.
In order to manage vast amount of information with great efficiency, there is a technology called autonomous distributed key-value store (KVS), which stores information pieces (values), each associated with a single key used in search operations, in a distributed manner across a plurality of locations (nodes). In such an autonomous distributed KVS system, an algorithm such as a Distributed Hash Table (DHT) or a Skip Graph is used in order to uniquely determine a node responsible for storing key-value pairs to thereby allow a search for the value associated with a given key.
In Chord, a DHT-based implementation, for example, each node is assigned, based on predetermined rules, to one of a plurality of identifiers (ID's) set in advance, and each key is assigned to a node according to the node assignment to the individual identifiers. That is, the node assignment and key assignment made in association with a node entry to or exit from the autonomous distributed KVS system are determined autonomously. Therefore, the autonomous distributed KVS system supports straightforward addition and removal of nodes, thereby providing high scalability.
There is a proposed technique for allowing flexible changes in data assignment by storing, in a node, key information and data in association with each other, managing the node in association with a range to which the hash value of the key information belongs, and making changes in the mapping of ranges to nodes in changing the storage location of the data. In addition, there is a proposed method of identifying the range to which the key of data stored in a node having exited (lost data) belongs by using information for managing the increase or decrease in nodes. Further, there is a proposed method of determining, in storing registration information pieces each including a key and original data of a data item corresponding to the key in DHT nodes, the order of the registration information pieces according to hash values of the keys and determining registration information pieces to be stored in the same node based on the determined order.
See, for example, the following documents:
Japanese Laid-open Patent Publication No. 2013-61739
Japanese Laid-open Patent Publication No. 2015-35182
Japanese Laid-open Patent Publication No. 2009-20757
David Karger et al., “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC '97), May 1997.
In an autonomous distributed KVS system, key-value (KV) pairs stored in a node are lost as the node exits. Therefore, the autonomous distributed KVS system replicates key-value pairs and stores the copies in a plurality of nodes, as in the above-mentioned proposed technique of Karger et al., to thereby prevent the loss of the key-value pairs. However, if frequent node entries and exits occur, high communication load between nodes (inter-node communication load) involved in replicating key-value pairs to other nodes is imposed.
In addition, each node entry or exit entails an update of information used for node searching. Therefore, frequent node entries and exits may result in high processing load of nodes. For example, in a system having, as its nodes, mobile terminals likely to enter and exit frequently, their communication environments may change over a short period of time and it may therefore frequently occur that a node having once exited re-enters the system shortly after the exit. Executing, for each re-entry, the same processing as for a new entry (such as replication of key-value pairs) may cause the inter-node communication load and the processing load of nodes to increase, leading to decreased performance of the system.